import java.util.HashMap;
import java.util.LinkedList;

/*
 * @lc app=leetcode.cn id=20 lang=java
 *
 * [20] 有效的括号
 */

// @lc code=start
class Solution {
    public boolean isValid(String s) {
        HashMap<Character,Character> dict=new HashMap<>();
        dict.put('(', ')');
        dict.put('[', ']');
        dict.put('{', '}');
        LinkedList<Character> data=new LinkedList<>();
        for (Character character : s.toCharArray()) {
            if (data.isEmpty()) {
                data.add(character);
            }
            else{
               if (dict.getOrDefault(data.peekFirst(), ' ')==character) {
                data.pollFirst();
               }
               else{
                data.addFirst(character);
               } 
            }
            
        }
        return data.size()==0;
    }

}
// @lc code=end

